//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组 单调栈 
// 👍 1433 👎 0



import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        if(0==length){
            return 0;
        }
        if(1==length){
            return heights[0];
        }

        int[] heightNew = new int[length+2];
        for(int i=0;i<length;i++){
            heightNew[i+1]=heights[i];
        }
        heights = heightNew;

        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0);
        for(int i=0;i<heights.length;i++){
            while(heights[stack.peekLast()]>heights[i]){
                int height = heights[stack.removeLast()];
                int width = i - stack.peekLast()-1;
                area = Math.max(area, height*width);
            }
            stack.addLast(i);
        }

        return area;

    }


    private int answer1(int[] heights){
        //暴力解法
        int length = heights.length;
        if(0==length){
            return 0;
        }
        if(1==length){
            return heights[0];
        }

        int area = 0;
        for(int i=0;i<length;i++){
            int minheight=Integer.MAX_VALUE;
            for(int j=i;j<length;j++){
                minheight = Math.min(heights[j],minheight);
                area = Math.max(area, minheight*(j-i+1));
            }

        }
        return area;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
